package LRU;

import org.testng.annotations.Test;
import org.testng.annotations.BeforeTest;


/**
 * LRU缓存测试类（使用JUnit 4框架）
 * 通过打印测试结果和状态信息验证功能正确性
 */
public class LRUCacheJUnit4Test {

    // 测试用的缓存容量
    private static final int CAPACITY = 10000;
    
    // 双向链表实现的LRU
    private LRUWithDoubleLinkedList<String, Integer> doubleLRU;
    
    // 单链表实现的LRU
    private LRUWithSingleLinkedList<String, Integer> singleLRU;

    /**
     * 每次测试前初始化两个LRU实例
     */
    @BeforeTest
    public void setUp() {
        doubleLRU = new LRUWithDoubleLinkedList<>();
        singleLRU = new LRUWithSingleLinkedList<>();
        
        // 初始化缓存
        doubleLRU.init(CAPACITY);
        singleLRU.init(CAPACITY);
    }

    /**
     * 测试初始化功能
     */
    @Test
    public void testInitialization() {
        System.out.println("=== 测试初始化 ===");
        
        // 检查初始状态
        System.out.println("双向链表实现 - 初始大小: " + doubleLRU.size() + " (预期: 0)");
        System.out.println("双向链表实现 - 是否已满: " + doubleLRU.isFull() + " (预期: false)");
        
        System.out.println("单链表实现 - 初始大小: " + singleLRU.size() + " (预期: 0)");
        System.out.println("单链表实现 - 是否已满: " + singleLRU.isFull() + " (预期: false)");
        
        // 测试非法容量
        System.out.println("\n测试非法容量初始化...");
        try {
            doubleLRU.init(0);
            System.out.println("双向链表实现 - 非法容量测试失败（未抛出异常）");
        } catch (IllegalArgumentException e) {
            System.out.println("双向链表实现 - 非法容量测试成功（正确抛出异常）");
        }
        
        try {
            singleLRU.init(-1);
            System.out.println("单链表实现 - 非法容量测试失败（未抛出异常）");
        } catch (IllegalArgumentException e) {
            System.out.println("单链表实现 - 非法容量测试成功（正确抛出异常）");
        }
        System.out.println("=== 初始化测试结束 ===\n");
    }

    /**
     * 测试基本的put和get操作
     */
    @Test
    public void testPutAndGet() {
        System.out.println("=== 测试put和get操作 ===");
        
        // 双向链表实现测试
        doubleLRU.put("key1", 100);
        doubleLRU.put("key2", 200);
        
        int doubleResult1 = doubleLRU.get("key1");
        int doubleResult2 = doubleLRU.get("key2");
        Integer doubleResult3 = doubleLRU.get("nonexistent");
        
        System.out.println("双向链表实现 - get(key1): " + doubleResult1 + " (预期: 100)");
        System.out.println("双向链表实现 - get(key2): " + doubleResult2 + " (预期: 200)");
        System.out.println("双向链表实现 - get(nonexistent): " + doubleResult3 + " (预期: null)");
        System.out.println("双向链表实现 - 当前大小: " + doubleLRU.size() + " (预期: 2)");
        
        // 单链表实现测试
        singleLRU.put("key1", 100);
        singleLRU.put("key2", 200);
        
        int singleResult1 = singleLRU.get("key1");
        int singleResult2 = singleLRU.get("key2");
        Integer singleResult3 = singleLRU.get("nonexistent");
        
        System.out.println("单链表实现 - get(key1): " + singleResult1 + " (预期: 100)");
        System.out.println("单链表实现 - get(key2): " + singleResult2 + " (预期: 200)");
        System.out.println("单链表实现 - get(nonexistent): " + singleResult3 + " (预期: null)");
        System.out.println("单链表实现 - 当前大小: " + singleLRU.size() + " (预期: 2)");
        System.out.println("=== put和get操作测试结束 ===\n");
    }

    /**
     * 测试更新已有key的值
     */
    @Test
    public void testUpdateExistingKey() {
        System.out.println("=== 测试更新已有key ===");
        
        // 双向链表实现
        doubleLRU.put("key1", 100);
        doubleLRU.put("key1", 1000); // 更新值
        int doubleResult = doubleLRU.get("key1");
        System.out.println("双向链表实现 - 更新后的值: " + doubleResult + " (预期: 1000)");
        System.out.println("双向链表实现 - 大小: " + doubleLRU.size() + " (预期: 1)");
        
        // 单链表实现
        singleLRU.put("key1", 100);
        singleLRU.put("key1", 1000); // 更新值
        int singleResult = singleLRU.get("key1");
        System.out.println("单链表实现 - 更新后的值: " + singleResult + " (预期: 1000)");
        System.out.println("单链表实现 - 大小: " + singleLRU.size() + " (预期: 1)");
        System.out.println("=== 更新已有key测试结束 ===\n");
    }

    /**
     * 测试缓存满时的淘汰机制
     */
    @Test
    public void testEvictionWhenFull() {
        System.out.println("=== 测试缓存满时的淘汰机制 ===");
        
        // 双向链表实现
        doubleLRU.put("key1", 1);
        doubleLRU.put("key2", 2);
        doubleLRU.put("key3", 3);
        doubleLRU.put("key4", 4);
        doubleLRU.put("key5", 5); // 缓存已满
        
        System.out.println("双向链表实现 - 是否已满: " + doubleLRU.isFull() + " (预期: true)");
        
        // 访问key2，使其成为最近使用的
        doubleLRU.get("key2");
        
        // 添加新元素，应该淘汰最少使用的key1
        doubleLRU.put("key6", 6);
        
        Integer doubleResult1 = doubleLRU.get("key1");
        Integer doubleResult2 = doubleLRU.get("key2");
        Integer doubleResult6 = doubleLRU.get("key6");
        
        System.out.println("双向链表实现 - get(key1): " + doubleResult1 + " (预期: null)");
        System.out.println("双向链表实现 - get(key2): " + doubleResult2 + " (预期: 2)");
        System.out.println("双向链表实现 - get(key6): " + doubleResult6 + " (预期: 6)");
        
        // 单链表实现
        singleLRU.put("key1", 1);
        singleLRU.put("key2", 2);
        singleLRU.put("key3", 3);
        singleLRU.put("key4", 4);
        singleLRU.put("key5", 5); // 缓存已满
        
        System.out.println("单链表实现 - 是否已满: " + singleLRU.isFull() + " (预期: true)");
        
        // 访问key2，使其成为最近使用的
        singleLRU.get("key2");
        
        // 添加新元素，应该淘汰最少使用的key1
        singleLRU.put("key6", 6);
        
        Integer singleResult1 = singleLRU.get("key1");
        Integer singleResult2 = singleLRU.get("key2");
        Integer singleResult6 = singleLRU.get("key6");
        
        System.out.println("单链表实现 - get(key1): " + singleResult1 + " (预期: null)");
        System.out.println("单链表实现 - get(key2): " + singleResult2 + " (预期: 2)");
        System.out.println("单链表实现 - get(key6): " + singleResult6 + " (预期: 6)");
        System.out.println("=== 缓存满时的淘汰机制测试结束 ===\n");
    }

    /**
     * 测试访问元素后更新其位置（最近使用）
     */
    @Test
    public void testAccessUpdatesOrder() {
        System.out.println("=== 测试访问顺序更新 ===");
        
        // 双向链表实现
        doubleLRU.put("key1", 1);
        doubleLRU.put("key2", 2);
        doubleLRU.put("key3", 3);
        
        // 访问key1，使其成为最近使用的
        doubleLRU.get("key1");
        
        // 添加新元素，应该淘汰最少使用的key2
        doubleLRU.put("key4", 4);
        doubleLRU.put("key5", 5);
        doubleLRU.put("key6", 6);
        
        Integer doubleResult2 = doubleLRU.get("key2");
        Integer doubleResult1 = doubleLRU.get("key1");
        
        System.out.println("双向链表实现 - get(key2): " + doubleResult2 + " (预期: null)");
        System.out.println("双向链表实现 - get(key1): " + doubleResult1 + " (预期: 1)");
        
        // 单链表实现
        singleLRU.put("key1", 1);
        singleLRU.put("key2", 2);
        singleLRU.put("key3", 3);
        
        // 访问key1，使其成为最近使用的
        singleLRU.get("key1");
        
        // 添加新元素，应该淘汰最少使用的key2
        singleLRU.put("key4", 4);
        singleLRU.put("key5", 5);
        singleLRU.put("key6", 6);
        
        Integer singleResult2 = singleLRU.get("key2");
        Integer singleResult1 = singleLRU.get("key1");
        
        System.out.println("单链表实现 - get(key2): " + singleResult2 + " (预期: null)");
        System.out.println("单链表实现 - get(key1): " + singleResult1 + " (预期: 1)");
        System.out.println("=== 访问顺序更新测试结束 ===\n");
    }

    /**
     * 测试异常情况处理
     */
    @Test
    public void testExceptionHandling() {
        System.out.println("=== 测试异常处理 ===");
        
        // 测试双向链表实现的异常处理
        System.out.println("双向链表实现 - 测试null key...");
        try {
            doubleLRU.get(null);
            System.out.println("双向链表实现 - get(null) 未抛出异常（错误）");
        } catch (NullPointerException e) {
            System.out.println("双向链表实现 - get(null) 正确抛出异常（正常）");
        }
        
        try {
            doubleLRU.put(null, 100);
            System.out.println("双向链表实现 - put(null, 100) 未抛出异常（错误）");
        } catch (NullPointerException e) {
            System.out.println("双向链表实现 - put(null, 100) 正确抛出异常（正常）");
        }
        
        // 测试单链表实现的异常处理
        System.out.println("单链表实现 - 测试null key...");
        try {
            singleLRU.get(null);
            System.out.println("单链表实现 - get(null) 未抛出异常（错误）");
        } catch (NullPointerException e) {
            System.out.println("单链表实现 - get(null) 正确抛出异常（正常）");
        }
        
        try {
            singleLRU.put(null, 100);
            System.out.println("单链表实现 - put(null, 100) 未抛出异常（错误）");
        } catch (NullPointerException e) {
            System.out.println("单链表实现 - put(null, 100) 正确抛出异常（正常）");
        }
        System.out.println("=== 异常处理测试结束 ===\n");
    }

    /**
     * 测试大量操作下的缓存行为
     */
    @Test
    public void testPerformanceDifference() {
        System.out.println("=== 高性能压力测试（突出链表性能差异） ===");
        final int OPERATIONS = 100000; // 增加到10万次操作
        final int ACCESS_RATE = 3; // 每3次操作就有1次访问，大幅提高访问频率
        long startTime, endTime;
        // 为两种实现使用相同的随机序列，确保测试公平性
        int[] randomKeys = new int[OPERATIONS / ACCESS_RATE];
        for (int i = 0; i < randomKeys.length; i++) {
            randomKeys[i] = (int)(Math.random() * (i * ACCESS_RATE + 1));
        }

        // 测试双向链表实现
        startTime = System.nanoTime(); // 使用纳秒级计时，提高精度
        int accessIndex = 0;
        for (int i = 0; i < OPERATIONS; i++) {
            doubleLRU.put("key" + i, i);

            if (i % ACCESS_RATE == 0 && i > 0) {
                doubleLRU.get("key" + randomKeys[accessIndex++]);
            }
        }
        endTime = System.nanoTime();
        System.out.println("双向链表实现 - 操作后大小: " + doubleLRU.size() + " (预期: " + CAPACITY + ")");
        System.out.printf("双向链表实现 - %d次操作耗时: %.3f秒\n",
                OPERATIONS, (endTime - startTime) / 1_000_000_000.0);
        double doubleTime = (endTime - startTime);

        // 测试单链表实现（使用相同的随机序列）
        startTime = System.nanoTime();
        accessIndex = 0;
        for (int i = 0; i < OPERATIONS; i++) {
            singleLRU.put("key" + i, i);
            if (i % ACCESS_RATE == 0 && i > 0) {
                singleLRU.get("key" + randomKeys[accessIndex++]);
            }
        }
        endTime = System.nanoTime();
        System.out.println("单链表实现 - 操作后大小: " + singleLRU.size() + " (预期: " + CAPACITY + ")");
        System.out.printf("单链表实现 - %d次操作耗时: %.3f秒\n",
                OPERATIONS, (endTime - startTime) / 1_000_000_000.0);

        // 计算性能差异倍数
        double singleTime = (endTime - startTime); // 实际运行时会替换为正确值
        System.out.printf("性能差异: 双向链表大约快 %.2f 倍\n", singleTime / doubleTime - 1);

        // 验证核心功能正确性（保留必要检查）
        System.out.println("双向链表实现 - 最新元素验证: " +
                (doubleLRU.get("key" + (OPERATIONS - 1)) == OPERATIONS - 1 ? "通过" : "失败"));
        System.out.println("单链表实现 - 最新元素验证: " +
                (singleLRU.get("key" + (OPERATIONS - 1)) == OPERATIONS - 1 ? "通过" : "失败"));
        System.out.println("双向链表实现 - 旧元素淘汰验证: " +
                (doubleLRU.get("key0") == null ? "通过" : "失败"));
        System.out.println("单链表实现 - 旧元素淘汰验证: " +
                (singleLRU.get("key0") == null ? "通过" : "失败"));

        System.out.println("=== 高性能压力测试结束 ===");
    }

}
    